package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	if root == nil || root == p || root == q {
		return root
	}
	left := lowestCommonAncestor(root.Left, p, q)
	right := lowestCommonAncestor(root.Right, p, q)
	if left != nil && right != nil {
		return root
	} else if left != nil {
		return left
	} else {
		return right
	}
}

func main() {
	node4 := &TreeNode{Val: 4, Left: nil, Right: nil}
	node5 := &TreeNode{Val: 5, Left: nil, Right: nil}
	node6 := &TreeNode{Val: 6, Left: nil, Right: nil}
	node7 := &TreeNode{Val: 7, Left: nil, Right: nil}
	node2 := &TreeNode{Val: 2, Left: node4, Right: node5}
	node3 := &TreeNode{Val: 3, Left: node6, Right: node7}
	root := &TreeNode{Val: 1, Left: node2, Right: node3}

	p := node4
	q := node7
	ancestor := lowestCommonAncestor(root, p, q)
	fmt.Println("最近公共祖先节点值为：", ancestor.Val)
}

